#include <bits/stdc++.h>

#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define in read<int>()
#define lin read<ll>()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pii >;

template < typename T > T read() {
	T x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-', ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }

const int N = 1e5 + 10;
const int B = 400;

int a[N];
int n, m;

pii pot1[N], pot2[N];
int top1, top2;

struct BLOCK {
	int xl, xr, tg, sz;
	pii arr[B + 10];
	void rebuild() {
		rep(i, xl, xr) arr[i - xl + 1].fi = a[i], arr[i - xl + 1].se = i;
		sort(arr + 1, arr + sz + 1);
	}
	void pd() { if(!tg) return; rep(i, xl, xr) a[i] += tg; rep(i, 1, sz) arr[i].fi += tg; tg = 0; }
	int getmx() { return arr[sz].fi + tg; }
	int getmn() { return arr[1].fi + tg; }
	void tadd(int l, int r, int v) {
		rep(i, l, r) a[i] += v;
		top1 = top2 = 0;
		rep(i, 1, sz) if(arr[i].se >= l && arr[i].se <= r) pot1[++top1] = arr[i], pot1[top1].fi += v;
		else pot2[++top2] = arr[i];
		merge(pot1 + 1, pot1 + top1 + 1, pot2 + 1, pot2 + top2 + 1, arr + 1);
		/*
		if(l == xl) inplace_merge(arr + 1, arr + r - xl + 2, arr + sz + 1);
		else assert(r == xr), inplace_merge(arr + 1, arr + l - xl + 2, arr + sz + 1);
		*/
	}
	int count(int lim) { if(lim < getmn()) return 0; if(lim > getmx()) return sz;
		return upper_bound(arr + 1, arr + sz + 1, pii(lim - tg, 1e9)) - arr - 1; }
} t[N / B + 10];

int bel[N];

void add(int l ,int r, int v) {
	int bl = bel[l], br = bel[r];
	if(bl == br) {
		t[bl].tadd(l, r, v);
		return;
	}
	t[bl].tadd(l, t[bl].xr, v); t[br].tadd(t[br].xl, r, v);
	rep(i, bl + 1, br - 1) t[i].tg += v;
}

const int inf = 0x3f3f3f3f;

int qkth(int l, int r, int k) {
	if(k > r - l + 1 || k < 1) return -1;
	int bl = bel[l], br = bel[r];
	if(bl == br) {
		t[bl].pd(); vec pot; rep(i, l, r) pot.eb(a[i]);
		sort(pot.begin(), pot.end());
		return pot[k - 1];
	}
	int L = inf, R = -inf, ans = -1;
	t[bl].pd(); t[br].pd(); rep(i, bl + 1, br - 1) chkmax(R, t[i].getmx()), chkmin(L, t[i].getmn());
	rep(i, l, t[bl].xr) chkmax(R, a[i]), chkmin(L, a[i]); rep(i, t[br].xl, r) chkmax(R, a[i]), chkmin(L, a[i]);
	if(k == 1) return L; if(k == r - l + 1) return R;
	vec pot; rep(i, l, t[bl].xr) pot.eb(a[i]); rep(i, t[br].xl, r) pot.eb(a[i]);
	sort(pot.begin(), pot.end());
	auto ct = [&](int lim) {
				  int cnt = int(upper_bound(pot.begin(), pot.end(), lim) - pot.begin());
				  rep(i, bl + 1, br - 1) cnt += t[i].count(lim);
				  return cnt;
				 };
	while(L <= R) {
		int mid = L + R >> 1;
		if(ct(mid) >= k) ans = mid, R = mid - 1;
		else L = mid + 1; 
	} return ans;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin); freopen("out.txt", "w", stdout);
#endif
	n = in, m = in; rep(i, 1, n) a[i] = in;
	rep(i, 1, n) bel[i] = (i - 1) / B + 1, t[bel[i]].xr = i;
	rep(i, 1, bel[n]) t[i].xl = t[i - 1].xr + 1, t[i].sz = t[i].xr - t[i].xl + 1, t[i].tg = 0, t[i].rebuild();
	while(m--) {
		int op = in, l = in, r = in, k = in;
		if(op == 1) printf("%d\n", qkth(l, r, k));
		else add(l, r, k);
	}
	return 0;
}
